This application claims priority of European Application No. 01300045.0 filed on Jan. 4, 2001.
1. Field of the Invention
The present invention relates to temporary data buffers, such as FIFO (first in, first out) buffers and stack buffers. Such buffers find application in many electronic devices, such as data-communication devices and computers.
2. Description of the Related Art
FIFOs are typically used for data rate adaptation i.e. data that is entering a system at a certain speed (bit rate) is adapted to the (different) speed of the systems clock rate by means of a FIFO. The rate adaptation to this fixed clock is realised by adding (or removing) justification data to (or from) the stream coming out of the system. This data is then transmitted e.g. over a glass fibre. At the receive side the justification data is added/removed again to reconstruct the original data stream.
In ATM (asynchronous transmission mode) systems, a cell stream may typically have a xe2x80x9cburstyxe2x80x9d nature i.e. ATM cells may randomly arrive in smaller or larger quantities per time unit. However to transport this traffic over larger distances (via fiber on e.g. a wide area network) the data needs to be adapted into a continuous data stream with a fixed bit rate. A FIFO can be used to handle this rate adaptation.
The FIFO is used as a temporary storage buffer (elastic store) to even out bursts. The size of a FIFO determines how much xe2x80x9cburstinessxe2x80x9d the FIFO can even out: usually the larger the better. However a large buffer size also often means a large latency (throughput delay) of the cells, which is undesirable in case of real-time traffic (CBR, rt-VBR). So an optimum in the size of a FIFO must be found between rate adaptation capacity and maximum throughput delay.
In ATM systems the data rate adaptation is also called cell rate decoupling. Justification is performed by adding so called xe2x80x9cIdlexe2x80x9d cells to a data stream. This is done in case there are no payload cells available i.e. when the FIFO is empty. In case the FIFO is full, no more cells are written in the FIFO, so just thrown away.
In PDH (Plesiochronous Digital Hierarchy) systems FIFOs are used to merge multiple bitstreams which are plesiochronous to one another into one single higher order bitstream. In this way:
four 2 Mb/s plesiochronous streams are merged into one 8 Mb/s stream
four 8 Mb/s plesiochronous streams are merged into one 34 Mb/s stream
four 34 Mb/s plesiochronous streams are merged into one 140 Mb/s stream
four 140 Mb/s plesiochronous streams are merged into one 565 Mb/s stream
The data rate adaptation is achieved by positive justification i.e., if required a data bit in the higher order bit stream can be replaced by a justification bit. So called xe2x80x9cJustification Controlxe2x80x9d bits are sent along with the data to indicate when a justification action needs to takes place. In this way the receiver is able to reconstruct the original tributary signal by removing the justification bit from the data stream. A justification action is required when the FIFO of a tributary stream is about to be depleted (underflow).
Although SONET (Synchronous Optical Network) and SDH (Synchronous Digital Hierarchy) systems deal with xe2x80x9csynchronousxe2x80x9d data, due to jitter and wander it is still required to align the data that are entering such a system and adapt the data-rate to an almost equal (but not quite) system clock. This is done by means of FIFOs. Also, here the adaptation is achieved by justification. Both positive justification (by removing stuff data) and negative justification (by adding stuff data) is possible.
Schematically, in a FIFO buffer data is entered at an entrance and is sent out at an exit in a sequence of xe2x80x9cfirst in, first outxe2x80x9d. During the time between the entrance and the exit the data is stored (buffered) in the FIFO. To that end, the FIFO consists of a memory device, which is capable of containing data. For the operation of the buffer, two counters are maintained. A first counter indicates the location of the memory cell, in which at a given instant data is to be entered or written. This first counter is referred to as the write-pointer. A second counter indicates the location of the memory cell, from which at a given instant data is to be sent out or read. This second counter is referred to as the read-pointer. By incrementing both pointers with a wrap-around from the highest memory location to the lowest, the entry- and exit-point xe2x80x9cmovexe2x80x9d through all memory locations in a continuous loop: the FIFO buffer can thus be used as a so-called circular buffer.
Typically, the memory device of a FIFO consists of an SRAM (static random access memory) device, in an arrangement with a single- or dual-port for accessing memory locations. In case of a dual-port SRAM, one port is used for entering data (write access port) and the other is used for exporting data (read access port). In a single-port SRAM one port has both functions, which are performed in an interleaved manner by a Time Division Multiple Access (TDMA) scheme.
Due to the relatively lower costs for single-port SRAMs, many FIFOs comprise single-port SRAM devices in stead of the more expensive dual-port SRAMs.
To obtain a throughput for a FIFO comprising a single-port SRAM in interleaved mode, comparable to that for a dual-port SRAM FIFO, the read and write access speed and the data bus width for such a single-port SRAM must be doubled in comparison to the specifications for the dual-port SRAM.
Characteristically for a FIFO, all data that need to pass the FIFO, must first enter the buffer through a write access port. In some cases, the insertion of additional data from a secondary source into the outgoing data stream is desired. For example, in ATM-PON (Asynchronous Transfer Modexe2x80x94Passive Optical Network) systems it is required to enter additional network operation and management data, i.e., PLOAM (Physical Layer Operations Administration and Maintenance) cells, into a data stream between the user ONT (Optical Network Termination) devices and a PON host system. Therefore, an additional write access port is needed on the FIFO. Adding this secondary write access to the FIFO is often very hard to implement, or even impossible. Especially, this problem occurs in dedicated circuitry, with hard-wired write and read pointers. No satisfying solution exists so far.
In case of a single-port SRAM device, when already a TDMA scheme is used for read and write access, the TDMA scheme must be extended for additional write slots on the single memory interface. This requires a higher access speed and a further widening of the data bus, in order to maintain the same throughput as without the additional access. Similarly, in a dual-port SRAM-based FIFO, a TDMA scheme may be used for additional write access cycles. Again, this requires higher access speed and widening of the data bus, to maintain the same throughput as without the additional access cycles. In both cases, this extension of the functionality of the device is often not feasible.
Also, replacement of a single-port SRAM by a dual-port SRAM is often not cost-effective, as mentioned above. Application of triple-port SRAM is, in most cases, even prohibitively expensive compared to single- or dual-port devices.
It is an object to provide an arrangement and method for a FIFO buffer device, which allows additional data from at least one additional data stream to be inserted into the outgoing data stream of the FIFO device without a requirement for additional ports on the FIFO device.
The present invention relates to a FIFO buffer arrangement for temporarily buffering a data packet from an incoming data stream before releasing the data packet into an outgoing data stream, comprising a memory device, a write pointer register, a read pointer register, the data packet containing a plurality of bytes; the memory device comprising a write access port and a read access port, the write pointer register containing a write pointer; the read pointer register containing a read pointer; the write pointer being arranged to indicate a first location in the memory device, momentary available for storing the data packet; the read pointer being arranged to indicate a second location in the memory device, momentary available for releasing a stored data packet to the out-going data stream; characterised in that the FIFO buffer arrangement further comprises a controller complex and additional memory, the controller complex being connected to the additional memory, to the memory device, and to the read pointer register, the additional memory being arranged to store at least one additional data packet, the controller complex being arranged to carry out the following functions:
continuously monitoring arrival of the at least one additional data packet in the additional memory;
storing a registered write pointer value each time at least one additional data packet arrives in the additional memory, the registered write pointer value having a predetermined relation with a momentary value of the write pointer at that time;
continuously monitoring a momentary value of the read pointer;
checking whether the read pointer has the predetermined relation with the registered write pointer value; if so, as an additional step:
reading the at least one additional data packet from the additional memory and inserting the at least one additional data packet in the outgoing data stream;
reading content from the second location in the memory device and inserting the content into the outgoing data stream.
Moreover, the present invention relates to a FIFO buffer arrangement as described above, characterised in that the FIFO buffer arrangement further comprises a selection device, a virtual cell insertion controller, data storage means, register memory means, an exit port, input means; the selection device being connected to the read access port and the exit port; the virtual cell insertion controller being connected to the write pointer register, the read pointer register, to the selection device, the data storage means, and the register memory means; the input means being connected to the data storage means and being arranged to insert an additional data packet into the data storage means; the register memory means is arranged to carry out the following steps:
to monitor continuously the arrival of the additional data packet in the data storage means;
to register the instant of arrival of the additional data packet by storing a momentary value, related to the instant of arrival, in the register memory device related to the data storage means as a registered write pointer value;
and the virtual cell insertion controller is also arranged to carry out the following steps:
to monitor continuously the momentary value of the read pointer;
to compare the value of the read pointer with the registered write pointer value stored in the register memory means;
on equality of the value of the read pointer and the registered write pointer value, to instruct the selection device to fetch the additional data packet from the data storage means related to the register memory means containing the registered write pointer value and, further, to transmit the additional data packet into the out-going data stream;
to instruct the selection device to fetch a byte from the second location in the memory device, the second location being indicated by the momentary value of the read pointer.
Furthermore, the present invention relates to a FIFO buffer arrangement as described above, characterised in that the memory device is a dual-port SRAM device.
Also, the present invention relates to a FIFO buffer arrangement as described above, characterised in that the memory device is a single-port SRAM device using a Time Division Multiple Access scheme.
Further, the present invention relates to a FIFO buffer arrangement as described above, characterised in that the data storage device and the register memory device are arranged as a combined register memory and data storage device.
Also, the present invention relates to a FIFO buffer arrangement as described above, characterised in that the virtual cell insertion controller and the selection device are arranged as a combined virtual cell insertion control and selection device.
The present invention further relates to a FIFO buffer arrangement as described above, characterised in that the virtual cell insertion controller, the selection device, the data storage device and the register memory device are arranged as a single combined controller device.
Moreover, the present invention relates to a FIFO buffer arrangement as described above, characterised in that the single combined controller device is an ASIC or FPGA.
The present invention also relates to a method to be carried out by a FIFO buffer arrangement, as described above, characterised in that the FIFO buffer arrangement further comprises a controller complex and additional memory, the controller complex being connected to the additional memory, to the memory device, to the write pointer register and to the read pointer register, the additional memory being arranged to store at least one additional data packet, and the method comprises the following steps:
to continuously monitor the arrival of the at least one additional data packet in the additional memory;
to store a registered write pointer value each time at least one additional data packet arrives in the additional memory, the registered write pointer value having a predetermined relation with a momentary value of the write pointer at that time;
to continuously monitor a momentary value of the read pointer;
to check whether the read pointer has the predetermined relation with the registered write pointer value; if so, as an additional step:
to read the at least one additional data packet from the additional memory and inserting the at least one additional data packet in the outgoing data stream;
to read content from the second location in the memory device and to insert the content into the outgoing data stream.
Moreover, the present invention relates to a computer program product to be loaded by a FIFO buffer arrangement, as described above, characterised in that
the FIFO buffer arrangement further comprises a controller complex and additional memory, the controller complex being connected to the additional memory, to the memory device, to the write pointer register and to the read pointer register, the additional memory being arranged to store at least one additional data packet, and
the computer program product, after being loaded, provides the FIFO buffer arrangement with the capacity to carry out the following steps:
to continuously monitor the arrival of the at least one additional data packet in the additional memory;
to store a registered write pointer value each time at least one additional data packet arrives in the additional memory, the registered write pointer value having a predetermined relation with a momentary value of the write pointer at that time;
to continuously monitor a momentary value of the read pointer;
to check whether the read pointer has the predetermined relation with the registered write pointer value; if so, as an additional step:
to read the at least one additional data packet from the additional memory and inserting the at least one additional data packet in the outgoing data stream;
to read content from the second location in the memory device and to insert the content into the outgoing data stream.
Also, the present invention relates to a data carrier provided with a computer program product as described above.